/*
题目: 将整数按权重排序
我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：

    如果 x 是偶数，那么 x = x / 2
    如果 x 是奇数，那么 x = 3 * x + 1

比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。

给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。

请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。

https://leetcode.cn/problems/sort-integers-by-the-power-value
 */
public class GetKth {
    public int getKth(int low, int high, int k) {
        int[] title = new int[high - low + 1];    // 存储范围内的元素
        int n = title.length;

        Integer[] index = new Integer[n]; // 存储元素对应的 下标
        for (int num = low, i = 0; num <= high; i++, num++) {
            title[i] = num;
            index[i] = i;
        }

        int[] w = new int[n]; // 储存 权重
        for (int i = 0; i < n; i ++) {
            w[i] = getWeight(title[i]); // 更新权重
        }


        Arrays.sort(index, new Comparator<Integer> () {
            public int compare(Integer o1, Integer o2) {
                if (w[o1] != w[o2]) { // 根据下标 按照 映射的权重排序, 如果权重相等, 按照 实际大小排序
                    return w[o1] - w[o2];
                }
                return title[o1]  - title[o2];
            }
        });

        return title[index[k - 1]];
    }

    private int getWeight(int x) {
        int step = 0;
        while (x != 1) {
            if ((x & 1) == 1)  // 奇数
                x = 3 * x + 1;
            else
                x /= 2;
            step++;
        }
        return step;
    }
}
